//
//  PermuteUnique.swift
//  LeetCodeSummary
//
//  Created by 彭西西 on 2020/6/25.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  47. 全排列 II 中等

import UIKit

/*
 47. 全排列 II
 难度
 中等

 321


 给定一个可包含重复数字的序列，返回所有不重复的全排列。

 示例:

 输入: [1,1,2]
 输出:
 [
   [1,1,2],
   [1,2,1],
   [2,1,1]
 ]
 */

class PermuteUnique: NSObject {
    
    var resultArr:[[Int]] = []
    
    func permuteUnique(_ nums: [Int]) -> [[Int]] {
        
        
        let boolArr = Array.init(repeating: false, count: nums.count)
        
        //先进行排序 这一点尤为重要
        //先进行排序 这一点尤为重要
        let nums = nums.sorted()
        //先进行排序 这一点尤为重要
        //先进行排序 这一点尤为重要
        //排序最主要的作用是把重复的元素放在一起 这样方便后面的去重操作。
        
        self.dfs(0, [], nums, boolArr)
        
        return resultArr
    }
    
    
    func dfs(_ startIndex:Int, _ tmpArr:[Int], _ sourceArr:[Int], _ flagArr:[Bool]){

        var arr = tmpArr
        var flagArr = flagArr
        
        if startIndex == sourceArr.count {
            print(arr)
            resultArr.append(arr)
            return
        }
        
        
        for index in 0 ..< sourceArr.count {
            if flagArr[index] == true {
                continue
            }
            if index > 0 && sourceArr[index] == sourceArr[index-1] && flagArr[index-1] == false {
                continue
            }
            
            arr.append(sourceArr[index])
            flagArr[index] = true
            
            self.dfs(startIndex + 1, arr, sourceArr, flagArr)
            
            arr.removeLast()
            flagArr[index] = false
        }
    }
}
